1. Field of the Invention
The present invention relates generally to methods and apparatuses for storing and retrieving binary information from a magnetic storage medium. More specifically, the invention relates to methods and apparatuses for encoding information according to a scheme which avoids storing catastrophic sequences of data which are difficult to recover on the magnetic disc.
2. Description of the Related Art
Digital magnetic and optical storage systems record digital sequences onto media. The sequences are retrieved from an analog signal, sensed by a readback head. Generally, the analog signal is corrupted by noise, interference, and distortion. The fundamental design goal of such systems is to achieve the highest recording density per unit area while maintaining an acceptable probability of error between the recorded and the retrieved sequences. In order to achieve this design goal, read/write channels use a combination of coding and equalization approaches as are described below.
Magnetic Storage Media
Data is commonly stored on magnetic storage media by altering the alignment of magnetic domains in the media. One example of a magnetic storage media is a magnetic storage disc. FIG. 1A is a schematic diagram which illustrates the alignment of magnetic domains on a typical data track 100 of a magnetic storage disc. As a readback head scans these domains, a signal is produced from which the state of the domains may be determined and the data stored in the domains may be derived.
Saturation recording is a commonly used technique in magnetic recording systems. Saturation recording means that the domains on the media are fully magnetized in one direction or an opposite direction. This is shown in FIG. 1A by the arrows which indicate the alignment of the magnetic domains at each storage location. The domains at a storage location 102, for example, are oriented in one direction and the domains at a storage location 104 are oriented in the opposite direction. The input signal which programs the storage locations is therefore binary. The sequence of input symbols are denoted a(n) and each a(n) is taken from the binary set {0,1}. The sequence of input symbols, a(n) is referred to as the media code sequence of symbols because it represents the symbols as they are written to the storage media. Because of the physical response of the reader head to the domains, the ideal, noise-free output z(n) of a readback head scanning such a magnetically recorded disc is complex.
FIG. 1B is a plot over time of an idealized read signal that would be produced by a readback head scanning the storage locations shown in FIG. 1A. When two successive storage locations have the same polarity, no output signal is produced. When the magnetic domains of two successive storage locations have opposite polarity, then a pulse is created and the difference in polarity of the change determined whether or not the pulse is positive or negative.
Recovery of the media code signal a(n) is possible by analyzing the media output signal z(n). As discussed below, z(n) is usually equalized to a signal x(n). As described below, in a maximum likelihood detection system, a Viterbi detector is used to determine the input sequence a(n) which is most likely to result in the x(n) which is input to the Viterbi detector.
Intersymbol Interference
One of the fundamental effects that limits the recording density in both magnetic and optical recording systems is intersymbol interference (ISI). ISI is the tendency of neighboring symbols as well as the symbol which is intended to be read at a given time to influence the output signal of the readback head. This effect is due to the bandlimited nature of the head/media combination and results in the overlap of responses due to sequentially recorded transitions on the media. That is, at a given instant in time, the output signal from the medium is composed of not only the response due to the input symbol at that instant, but also the responses from some previously recorded symbols. The amount and the span of this overlap increases as the linear recording density is increased, giving rise to overlap patterns among symbols that are generally very complex and hard to unravel with a simple device.
As symbols are stored more closely together, intersymbol interference makes it more and more difficult for individual symbols to be detected. Intersymbol interference is the tendency of the output of the readback head to be a function of both the readback head response to the symbol being read and also the response of the readback head to neighboring symbols. As symbols are stored closer and closer together, the response of the readback head may become an increasingly complex function of a number of sequentially recorded symbols. As the influence of neighboring symbols increases on the readback signal, it is increasingly likely that an error may be caused by intersymbol interference when reading a symbol.
Partial Response Signaling
In order to reduce the complexity required to unravel the ISI effect, a special signaling method, partial response (PR) been developed. PR signaling is described in H. K. Thapar and A. M. Patel, "A Class of Partial Response Systems for Increasing Storage Density in Magnetic Recording," IEEE Trans. on Magnetics, vol. 23, no. 5, pp. 3666-3668, September 1987, which is herein incorporated by reference for all purposes and will hereinafter be referred to as Reference 1. The readback signal is first equalized to a prescribed PR signal x(n). The equalization filter is designed so that the combination of the media channel and equalization transforms the data signal into the PR signal, x(n). PR signals allow for controlled overlap (or interference) of responses in the output signal due to successive input symbols. The a priori knowledge of the controlled ISI after the equalizer results in a significant reduction in the complexity of the required detector relative to that for the unequalized signal. The detector used is called a Viterbi detector. Sampled signal levels from the readback head are input to the Viterbi detector which determines the most probable input data, thus the Viterbi detector is referred to as a "maximum likelihood" detector and the method is called "partial response, maximum likelihood" (PRML).
The choice of the PR target signal is not unique, but dictated by the operating linear density. Indeed, many PR targets exist for the magnetic recording application as discussed in Reference 1. The first generation of Read Channel devices employing PR targets was based on the use of Class IV Partial Response signaling, referred to commonly as PRML (Partial Response Maximum Likelihood). As described in Reference 1, the focus of new generation devices is on Extended Partial Response Maximum Likelihood or EPRML. In an EPRML system, as in a PRML system, the input is binary, but five output levels instead of three are sensed so that the output is contained in the set {-2,-1,0,+1,+2}. The five sensed output levels provide information about the output which enables the Viterbi detector to determine the most likely sequence of stored inputs from the output. An advantage of EPRML is that it implements an equalization filter with a lower response at high frequencies and therefore avoids amplifying certain high frequency noise.
FIG. 2 is a block diagram illustrating a PRML system. A signal a(n) is the media code signal at time nT, where T is the channel symbol duration. The signal a(n) over time represents the sequence of binary symbols which are to be stored on and recovered from a magnetic storage channel 200. Magnetic storage channel 200 is also referred to as the media channel. After passing through magnetic storage channel 200 and an equalization filter 202, a(n) is transformed into x(n). For a PRML system where the signal is equalized to the Class IV Partial Response and the maximum-likelihood (ML) detection is performed with the Viterbi detector as described in Lee and Messerschmitt, Digital Communication, Kluwer Academic Press 1994. which is herein incorporated by reference for all purposes and will hereinafter be referred to as Reference 2, the equalized noise-free sampled output is given by the difference equation: EQU x(n)=a(n)-a(n-2) Equ. 1
where x(n) is the output sample value at time nT, a(n) is the media code at time nT, and T is the channel symbol duration. The input symbols a(n) are picked from the binary set {0,1}. The noise-free output sample values are ternary, namely, 0, +1, or -1. Equ. 1 is referred to as the partial response polynomial and may also be represented as the transfer function 1-D.sup.2 where D represents 1 unit time delay. 1-D.sup.2 is the standard PRML transfer function that describes the result of the prescribed intersymbol interference that characterizes PRML. The inverse of 1-D.sup.2 is represented as 1/(1-D.sup.2).
Equ. 1 thus is represented by a standard PRML transfer function which describes the output of the equalization filter when the signal is equalized to the Class IV Partial Response. Other transfer functions exist for other systems which implement different partial response targets. For example, the transfer function for EPRML which describes the output of the Viterbi detector when the signal is equalized to the Extended Class IV Partial Response is 1+D.sup.1 -D.sup.2 -D.sup.3 and is derived according to the extended partial response polynomial: EQU x(n)=a(n)+a(n-1)-a(n-2)-a(n-3) Equ. 2
This equation will be discussed in detail later. In PRML systems where the equalized noise-free sampled output is given by Equ. 1, it is necessary to undo the transformation that is described by Equ. 1 in order to recover the data sequence a(n) which was stored on the magnetic medium. In Class IV Partial Response PRML systems, this is accomplished using a preceding step.
FIG. 3 is a block diagram illustrating a Class IV Partial Response PRML system which stores and recovers data from a user. A user signal u(n) represents actual data which is written to and recovered from the magnetic recording system. User signal u(n) is input to a modulation encoder 302 which encodes the signal as a binary signal c(n). The output of modulation encoder 302, c(n), is referred to as the channel code because it represents the actual code or signal which is written to the storage system.
If the channel code c(n) were written directly to the media, then the output after equalization, x(n) would be determined by c(n) according to the PRML partial response polynomial. In PRML systems, a precoder is used that inverts the effect of the PRML media channel and equalization so that the output after equalization is c'(n). It should be noted that c'(n) is not exactly identical to c(n), because c'(n) is not a binary signal, and generally has more than two allowed states. However, as will be seen below, each allowed state of c'(n) converts directly to one of the allowed binary values of c(n). The output of modulation encoder 302 is sent to a precoder 304. Precoder 304 implements a channel inverting transfer function which is a transfer function which is the inverse of the standard EPRML transfer function. The output of precoder 304, a(n), is written to a media channel 306.
When the media is read, a signal z(n) is obtained which represents the channel code c(n) transformed by the precoding and the media write and read processes. The signal z(n) is input to an equalizer 308 which outputs a signal c'(n). The signal c'(n) is the result of the transformation of the signal by media channel 306 and equalizer 308 and the preceding of c(n) by precoder 304 according to the channel inverting transfer function. A Viterbi detector determines the sequence of channel code c(n) which was most likely to have been written to media channel 306 via precoder 304, given the c'(n) that was detected. A decoder 314 converts c(n) to u'(n), the recovered signal which, if the system is successful differs from signal u(n) stored by the user by less than some allowable error tolerance.
Precoder 304 functions to invert the effect of the media channel combined with the equalization. That is, for a PRML system, the transfer function of precoder 304 is 1/(1.sym.D.sup.2). When such a precoder implemented, then the effect of the Class IV Partial Response PRML system is essentially to undo the transformation implemented by the precoder and the output of the Class IV Partial Response PRML system, c'(n), maps directly to the channel code.
According to equation 1, the equalized output is EQU x(n)=a(n)-a(n-2) Equ. 1
To invert the transfer function 1-D.sup.2, solve for a(n), obtaining: EQU a(n)=x(n)+a(n-2) Equ. 3
Substituting c(n) for x(n), the equation which governs the precoder is derived: EQU a(n)=c(n)+a(n-2) Equ. 4
It should be noted that in modulo 2, addition and subtraction are both expressed by the exclusive or operation denoted by .sym.. That is: EQU a+b=a-b=a.sym.b.
FIG. 4A is a chart which shows that when precoding is performed according to: EQU a(n)=c(n).sym.a(n-2), Equ. 5
then the absolute value of the output of the equalizer, x(n), (which is denoted as c'(n)) is equal to the channel code c(n). It is shown that this is true for all possible values of c(n), a(n), and a(n-2). The effect of the preceding step on a channel code signal c(n) is to cause c'(n) to be recovered after the known transformation caused by the media channel and equalization. Thus, when the precoder implements a transfer function which is the inverse of the standard PRML transfer function, the precoder inverts the channel and the absolute value of the output of the equalizer is the same as the channel code.
Similarly, a precoder could be designed for an EPRML system which inverts the channel.
According to equation 2, the equalized output of the equalizer for an EPRML system is: EQU x(n)=a(n)+a(n-1)-a(n-2)-a(n-3) Equ. 2
The transfer function of the system would therefore be: EQU 1+D-D.sup.2 -D.sup.3
To invert the transfer function 1+D-D.sup.2 -D.sup.3, solve for a(n), obtaining: EQU a(n)=x(n)-a(n-1)+a(n-2)+a(n-3) Equ. 6
Substituting c(n) for x(n), the equation which governs the precoder is derived: EQU a(n)=c(n)-a(n-1)+a(n-2)+a(n-3) Equ. 7
Again, it should be noted that in modulo 2, addition and subtraction are both expressed by the exclusive-or operation. Therefore, if a precoder is used which implements the equation: EQU a(n)=c(n).sym.a(n-1).sym.a(n-2).sym.a(n-3) Equ. 8
then the channel will be inverted by the precoder and the channel bits can be recovered by taking the absolute value of x(n) modulo 2.
FIG. 4B is a chart which shows that when precoding is performed according to: EQU a(n)=x(n).sym.a(n-1).sym.a(n-2).sym.a(n-3), Equ. 8
then the absolute value of the output modulo 2 of the equalizer x(n) ignoring noise (which is denoted as c'(n)) is equal to the channel code c(n). It is shown that this is true for all possible values of c(n), a(n), a(n-1), a(n-2), and a(n-3). Thus, when a(n), the binary output of the precoder is determined as a function of c(n), the binary channel bits, as well as the previous values of a(n) as described by Equ. 6, then the absolute value in modulus 2 of the output of the media channel and the equalizer, c'(n) is the same as the channel bits. Thus, as was shown above for the PRML precoder and the PRML channel, the EPRML precoder described above implements a transfer function which is the inverse of the standard EPRML transfer function and therefore inverts the EPRML channel.
RLL Codes--Avoiding Long Periods Between Signal Transitions
As described above, the output of modulation encoder 302 and precoder 304 is a media code sequence a(n). Certain sequences of media code are problematic for the system and must be avoided. For example, a long sequence of zeros can thwart the timing and gain update loops used to calibrate the reader.
As the readback head scans the recording medium, the timing of the sampling and the gain of the signal must constantly be updated to ensure that sampling occurs at the right point for each memory location and that the gain is adjusted to allow for changing media characteristics that affect the signal strength. If the channel code sequence repeatedly writes zero to the disk, then no signal is available to update the timing or gain loops and system degradation can result.
Currently, Digital magnetic and optical storage devices use run length limited (RLL) codes to improve signal detectability or insure frequent updates to the timing and gain loops, or both. The RLL codes are generally characterized by two parameters, d and k, which control, respectively, the minimum and the maximum number of symbol intervals between successive transitions in the binary input signal. For a given value of d, the RLL code insures that there are at least (d+1), and at most (k+1), symbol intervals between successive transitions. Commonly used codes in magnetic and optical storage products include codes with (d,k) constraints of (1,7) and (2,7). These codes are typically used with the Peak Detection method. The k constraint insures that a non-zero channel output is produced with some minimum frequency to maintain robust operation of timing and gain loops. The d constraint helps signal detectability with peak detection. With the growing interest in Partial Response Maximum Likelihood (PRML) techniques, d=0 codes are gaining in popularity because of their inherently higher code rates.
Catastrophic Sequences and Coding For PR Signaling
In addition to ensuring that timing and gain update information are provided, choosing a coding scheme which does not produce a response at the reader head caused by one sequence of media code which can easily be confused for a long number of samples with a response caused by a different sequence of media code is important with partial response signaling to achieve a prescribed performance within the constraints of a given hardware complexity. Catastrophic sequences of code which create a readback signal which varies by only a small amount must be avoided in PR systems to avoid creating long strings of readback signal which are not distinguishable by the Viterbi detector. When such long strings occur, the Viterbi detector must have a memory that is sufficiently large to store the strings until the most likely state of the stored data can be determined.
Consider the PRML system wherein the signal is equalized to the Class IV Partial Response (PR) and the maximum-likelihood (ML) detection is performed with the Viterbi detector as described in Reference 2. As noted above, The equalized noise-free sampled output is given by the difference equation: EQU y(n)=a(n)-a(n-2) Equ. 1
where y(n) is the sample value at time nT, a(n) is the input symbol at time nT, and T is the channel symbol duration.
The Viterbi detector observes the noisy version of y(n) to produce estimates of the input sequence a(n). It performs the estimation recursively by comparing the received sample sequence against all allowed noise-free sample sequences, computing their differences in terms of the sum-of-squared-errors, and picking the noise-free sequence with the smallest difference. The performance of the Viterbi detector, computed in terms of the probability of error at moderate to high signal-to-noise ratio (SNR), is largely determined by the minimum Euclidean distance between sequences forming an error event, where an error event refers to a pair of noise-free sampled output sequences generated by paths that diverge from a common state and later remerge at a common state. FIG. 5A is a trellis diagram illustrating an error event for PRML where the paths with labels 1 0 and 0 1 diverge from the common state 0 and remerge at state 1. The associated squared-Euclidean distance is 2. It can be verified that the minimum squared-Euclidean distance for PRML is 2.
In order to guarantee the minimum distance properties for PRML, coding of the input data to avoid certain sequences is necessary. FIG. 5B is a trellis diagram illustrating an error event for PRML where the paths diverge from a common state 0 and do not remerge for some time. The input data sequence is 00000 . . . 000. Such a sequence traces a path on the trellis comprising the output sampled sequence of all zero. The correct sequence can be confused with the input sequence 11111 . . . 110 to produce a minimum distance error event shown in FIG. 5B. If the path memory in the Viterbi detector is not long enough and prematurely truncated, the accumulated distance between the two allowed sequences would be 1, as shown in FIG. 1(b), resulting in performance degradation. The two paths would therefore be confused by the Viterbi detector because the path memory of the Viterbi detector is not long enough.
Pairwise sequences of unbounded length (and their associated paths) within the trellis that do not accumulate the full minimum distance are referred to as catastrophic sequences. FIG. 5C is a trellis diagram illustrating an error event for PRML where the paths diverge from a common state 0 and do not remerge within a path memory length 500. Such an error event is referred to as an open error event and would not be detected by a Viterbi detector with path memory length 500.
Coding can be used to eliminate such sequences, and thereby effect the realization of the full minimum distance over some prescribed memory path maximum length. That is, the coding of the signal being stored can be selected to prevent the storage of a catastrophic sequence. In the example shown in FIG. 5C, coding could be used to prevent the storage of a greater number of consecutive zeros than the length of the Path Memory. For a given a transfer function such as 1-D.sup.2, what is needed is some form of coding that will prevent catastrophic sequences from occurring. When a precode is used which inverts the channel such as is described above, then constraining the modulation code to not include catastrophic sequences prevents a signal which represents a catastrophic sequence from being produced at the readback head. It is most desirable that any constraints incorporated into the modulation code be relatively simple so that a modulation code which obeys the constraints may be readily created.
Thus, the maximum length required for the realization of the full minimum distance may be defined by the proper choice of a modulation code together with a precode. This maximum length also determines the survivor memory requirements within the Viterbi detector. In general, the goal of the code design is to minimize the maximum length required. The design of modulation codes for PRML channels is described in Marcus, Siegel, and Wolf, "Finite State Modulation Codes for Data Storage," IEEE Journal of Selected Areas in Communications, vol. 10, no. 1, pp. 5-37, January 1992, which is herein incorporated by reference for all purposes and will hereinafter be referred to as Reference 3 and in Eggenberger and Patel, U.S. Pat. No. 1,707,681, issued November 1987, which is herein incorporated by reference for all purposes and will hereinafter be referred to as Reference 4.
Unlike RLL codes for peak detection which require only a minimum and a maximum run lengths as constraints, the PRML codes generally do not require a minimum run length (that is, d=0) but do require additional constraints on the recorded sequences to guarantee minimum distance error events of bounded length.
In view of the foregoing, what is needed is a modulation encoding scheme for EPRML that will prevent catastrophic sequences from occurring. When a precoder which uses the channel inverting transfer function as described above is used, it is difficult to design such a modulation encoding scheme that directly limits the maximum length required for the realization of the full minimum distance in EPRML. Another approach to designing a modulation encoding scheme is needed.